package leetcode_day._2022._202203._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/3/11 19:48
 * 统计最高分的节点数目
 * 算法：深度优先搜索
 * 使用两个数组记录节点的左右子树
 * 从叶子节点开始计算子节点的数量，就是后序遍历
 */
public class _11_2049 {

    int ans = 0, n;
    long max = 0;

    public int countHighestScoreNodes(int[] parents) {
        this.n = parents.length;
        int[] lefts = new int[n], rights = new int[n];
        for (int i = 0; i < n; i++) {
            lefts[i] = -1;
            rights[i] = -1;
        }
        for (int i = 1; i < n; i++) {
            int p = parents[i];
            if (lefts[p] == -1) lefts[p] = i;
            else rights[p] = i;
        }
        dfs(0, lefts, rights);
        return ans;
    }

    public int dfs(int node, int[] lefts, int[] rights) {
        // 当之前的节点是叶子节点时，这里才会是 0
        if (node == -1) return 0;
        int leftCnt = dfs(lefts[node], lefts, rights);
        int rightCnt = dfs(rights[node], lefts, rights);
        int remain = n - leftCnt - rightCnt - 1;
        long score = help(leftCnt) * help(rightCnt) * help(remain);
        if (score == max) {
            ans++;
        } else if (score > max) {
            max = score;
            ans = 1;
        }
        return leftCnt + rightCnt + 1;
    }

    // 这里要返回 long，不然相乘还是 int
    public long help(int cnt) {
        return cnt == 0 ? 1 : cnt;
    }

}
